This invention relates generally to a method and apparatus for improving performance in systems where multiple processors contend for control of a shared resource through a queued lock associated with the shared resource, and more particularly to a method and apparatus for improving performance in intelligent data storage systems.
When a computer system resource is shared by multiple processes running on multiple processors, or even on one processor, often there must be some way of insuring that no more than one such process may access that resource at any one time. In designing complex data storage systems including multiple processors, synchronizing access to shared resources has been recognized as an issue which must be addressed in order to maintain the consistency and validity of the data. However, the sharing issue may arise in connection with almost any resource than might be used by multiple requestors.
Many high-performance storage systems are intelligent data storage systems which may be accessible by multiple host computers. These may include, in addition to one or more storage device arrays, a number of intelligent controllers for controlling the various aspects of the data transfers associated with the storage system. In such systems, host controllers may provide the interface between the host computers and the storage system and device controllers may be used to manage the transfer of data to and from an associated array of storage devices (e.g. disk drives). Often, the arrays may be accessed by multiple hosts and controllers. In addition, advanced storage systems, such as the SYMMETRIX(copyright) storage systems manufactured by EMC Corporation, typically include at least one shared resource in the form of a global memory which is coupled to each of the controllers in the system. The memory may be used as a staging area (or cache) for the data transfers between the storage devices and the host computers and may provide a communications path between the various controllers. Various communication channels, such as busses, backplanes or networks, link the controllers to one another and the global memory, the host controllers to the host computers, and the disk controllers to the storage devices.
To provide reliable access by any host over any host channel to any of the data stored in the data storage devices, it is necessary to coordinate all of the host and device controllers in the system with each other. To simplify this coordination, the global memory is used as a buffer for data transfer between each host controller and each disk controller. Such systems are described, for example, in Yanai et al, U.S. Pat. No. 5,206,939 issued Apr. 27, 1993, (hereinafter xe2x80x9cthe ""939 patentxe2x80x9d), Yanai et al, U.S. Pat, No. 5, 381,539 issued Jan. 10, 1995, (hereinafter xe2x80x9cthe ""539 patentxe2x80x9d), Vishlitzky et al, U.S. Pat. No. 5,592,432 issued Jan. 7, 1997, (hereinafter xe2x80x9cthe ""432 patentxe2x80x9d), Yanai et al, U.S. Pat. No. 5,664,144 issued Sep. 2, 1997 hereinafter xe2x80x9cthe ""144 patentxe2x80x9d), and Vishlitzky et al, U.S. Pat. No. 5,787,473 issued Jul. 28, 1998, (hereinafter xe2x80x9cthe ""473 patentxe2x80x9d), all of which are herein incorporated in their entirety by reference. The systems described therein provide for distributed management of the global memory resources by the controllers. In these systems, the consistency of the data contained in some portions of global memory is maintained by allowing each controller to lock those data structures which require consistency while it is performing operations which are supposed to be atomic on them.
Typically, synchronization of access to a shared resource, such as the global memory in the systems described above, is accomplished by associating a lock with the resource. Queued lock management allows a processor which initially fails to obtain the lock to queue for subsequent access. Lock management, including the design and operation of lock request queues, is well known in the art, as described, for example, in Transaction Processing: Concepts and Techniques, Jim Gray and Andreas Reuter, Morgan Kaufmann Publishers, 1993 edition; Operating System Concepts, Abraham Silberschatz and Peter Baer Galvin, Addison-Wesley, 1998 edition: xe2x80x9cResource Allocation with Immunity to Limited Process Failurexe2x80x9d, Michael J. Fischer, Nancv A. Lynch. James E. Burns, and Alan Borodin, 20th Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, October ""79, p 234-254; and xe2x80x9cDistributed FIFO Allocation of Identical Resources Using Small Shared Spacexe2x80x9dACM Transactions on Programming Languages and Systems, January ""89, 11(1): 90-114. The lock request queue is a data structure which indicates the current holder of the lock and the priority of unsuccessful lock requests. Generally, the lock request queue must be implemented in a section of memory that is also shared, or at least accessible, by all of the processors which might need access to the shared resource, although it need not be on the same media as the shared resource. The procedures which allocate the lock may be centralized or distributed. In the intelligent data processing systems described above, the lock allocation procedures are typically distributed among the various intelligent controllers.
To obtain the lock for a resource, each requestor from among the processors, such as one of the controllers, must first invoke a lock allocation procedure to attempt to obtain the lock. If it is not awarded the lock, its request will be entered in the lock request queue in accordance with a predetermined priority algorithm. To determine the status of its request, the requester must poll for the lock over the communication channel which links the two. If the lock is not available, the requester must wait, typically for a predetermined, fixed period, and poll again, repeating the loop until the lock is obtained. To minimize resource latency, i.e. xe2x80x9cdeadxe2x80x9d intervals between the time when one processor relinquishes the lock and the next processor obtains it, the polling frequency is typically fixed at a relatively high value. In large systems with high activity, however, high polling rates can saturate communication channels and memory with unproductive calls, thereby seriously degrading the performance of the entire system. In some systems, a separate channel has been dedicated to lock requests in order to avoid these problems. However, this solution has the disadvantage of reducing system throughput by largely eliminating the lock request channel as a resource for productive data transfer within the system.
It would be advantageous therefore to provide a method and apparatus capable of dynamically varying the polling frequencies of multiple unsuccessful requesters in order to reduce both latency and saturation problems without requiring a dedicated lock request channel or otherwise reducing system performance.
The invention provides a method and apparatus for improving performance in computer systems, and preferably intelligent data storage systems, where a queued lock prioritizes requests for access to a shared resource by contending requesters. In general, the invention provides that when each unsuccessful requestor periodically polls a lock request queue for information on the status of its pending lock request, it obtains information on its priority in the lock request queue and adaptively delays its next poll by a period determined as a function of this priority. In some aspects, the period is also a function of the average duration of a significant operation involving the shared resource. Typically, each unsuccessful requestor estimates, upon each poll, the number of prior entries in the lock request queue and adaptively determines its polling period as a function of the number of prior entries in the lock request queue. In some aspects, the requester may record the duration of one or more of its periodic polls of the lock request queue, and estimate the average duration of a significant processor operation involving the shared resource as a function of one or more of the polling durations it records.
The computer system typically includes multiple processors as requestors, and these are coupled to a shared resource through one or more first common communication channels. A lock allocation procedure is implemented in each of the processors to enable each processor to request locks on the shared resource by each processor and determine, in accordance with a predetermined priority algorithm, the priority of its unsuccessful lock requests.
A lock request queue, responsive to these lock allocation procedures, is implemented in a shared memory accessible over one or more second common communications channels to all of the processors. The lock request queue identifies a successful requester from among the processors as the current holder of the lock on the shared resource, and further indicates the priority of requests for subsequent locks on the shared resource by one or more unsuccessful requestors from among the processors. Each unsuccessful requestor implements a lock polling delay procedure that periodically polls the lock request queue for information on both the status and the priority of the requestor""s pending lock request and adaptively determines the requestor""s polling period as a function of its priority in the lock request queue. In one aspect, the lock polling delay procedure may also determine the requestor""s polling period as a function of the average duration of a significant processor operation involving the shared resource. In another aspect, if the lock request queue is accessed over the same channel as the shared resource, the lock polling delay procedure may record the duration of one or more of its periodic polls of the lock request queue, and the polling durations recorded by the polling delay procedure may be used to estimate the average duration of a significant processor operation involving the shared resource.
In one aspect, the invention provides a method of improving performance in systems wherein multiple controllers may access a shared data resource through at least one first common channel and priority of access to the shared data resource is determined through a queued lock. Each controller requests a lock on the shared data resource by invoking its lock allocation procedure. A lock request queue implemented in a shared memory accessible over at least one second common channel to all of the controllers identifies a successful requestor from among the controllers as the current holder of the lock on the shared data resource, and further indicates the priority of requests for subsequent locks on the shared resource by one or more unsuccessful requestors from among the controllers. The method comprises the following steps. First, the controllers make multiple requests for locks on the shared data resource. A successful requestor from among the controllers obtains the lock and is identified as the current holder of the lock in the lock request queue. Each unsuccessful requester from among the controllers stores its request for a lock on the shared data resource in the lock request queue in accordance with a predetermined priority algorithm. An unsuccessful requestor from among the controllers polls the lock request queue. The unsuccessful requestor determines whether it has become the current holder of the lock and, if not, the estimated number of prior entries in the lock request queue. It then finds as a function of the estimated number of prior entries in the lock queue, the number of significant operations expected to be performed before the unsuccessful requestor obtains the lock. It finds the average duration of a significant processor operation involving the shared resource. The unsuccessful requester calculates the expected duration of the wait before the unsuccessful requestor obtains the lock. This wait is determined as the product of the previously found average duration of a significant processor, i.e. controller, operation involving the shared resource and the previously found number of significant operations expected to be performed. The unsuccessful requestor delays for the expected duration of the wait before repeating its poll. Each unsuccessful processor repeats the polling, determining priority, finding expected number of significant operations, finding average duration, wait calculation and delaying steps until it obtains the lock.
In a preferred aspect, each unsuccessful requestor may poll the lock request queue through one or more of the first common channels and records the duration of one or more of such polls. During the step of finding the average duration of a significant processor operation involving the shared resource, the unsuccessful requestor estimates the average duration of a significant processor operation involving the shared resource as a function of one or more of the polling durations recorded by the unsuccessful requestor.
In another preferred aspect, an intelligent data storage system includes multiple controllers coupled to a shared data resource through one or more first common channels. A lock allocation procedure is implemented in each of the controllers and associated with the shared data resource, for requesting a lock on the shared resource by each the controller and determining in accordance with a predetermined priority algorithm the priority of each controllers unsuccessful lock requests. A lock request queue, responsive to the lock allocation procedures, is implemented in a shared memory accessible over at least one second common channel to all of the controllers. The lock request queue identifies a successful requester from among the controllers as the current holder of the lock on the shared resource, and further indicates the priority of requests for subsequent locks on the shared resource by one or more unsuccessful requestors from among the controllers.
Each of the unsuccessful requestors implements in its lock allocation procedure a lock polling delay procedure that periodically polls the lock request queue for information on the status and priority of its pending lock request and adaptively determines the unsuccessful requestor""s polling period as a function of its priority in the lock request queue. The function which determines the unsuccessful requestor""s polling period as a function of its priority in the lock request queue may be the product of the number of significant processor, i.e. controller, operations expected to be performed before the unsuccessful requester obtains the lock as a function of the number of prior entries in the lock request queue and the average duration of a significant processor, i.e. controller, operation involving the shared resource. If the first and second common communication channels are the same, as they are in one preferred aspect of the invention, and each of the unsuccessful requestors records during its lock polling delay procedure the duration of one or more of its periodic polls, the average duration of a significant processor operation involving the shared resource may be estimated as a function of one or more of the polling durations recorded by the unsuccessful requestor.
In yet another aspect of the invention, multiple processes running on a single processor may in some aspects act as requesters, and a lock allocation process or procedure may be invoked by each of these processes, but the operation of the invention is otherwise as described above.